package com.atguigui.leetcode1;

/**
 * 1080.根到叶路径上的不足节点
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/5/22 9:07
 */
public class P1080InsufficientNodesInRootToLeafPaths {

    public static void main(String[] args) {
        Solution solution = new P1080InsufficientNodesInRootToLeafPaths().new Solution();
        // TO TEST
    }
    //leetcode submit region begin(Prohibit modification and deletion)


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    class Solution {
        public TreeNode sufficientSubset(TreeNode root, int limit) {
            boolean haveSufficient = checkSufficientLeaf(root, 0, limit);
            return haveSufficient ? root : null;
        }

        public boolean checkSufficientLeaf(TreeNode node, int sum, int limit) {
            if (node == null) {
                return false;
            }
            if (node.left == null && node.right == null) {
                return node.val + sum >= limit;
            }
            //进行累加
            boolean haveSufficientLeft = checkSufficientLeaf(node.left, sum + node.val, limit);
            boolean haveSufficientRight = checkSufficientLeaf(node.right, sum + node.val, limit);

            if (!haveSufficientLeft) {
                node.left = null;
            }
            if (!haveSufficientRight) {
                node.right = null;
            }
            return haveSufficientLeft || haveSufficientRight;
        }
    }

}
